package com.gwcloud.leetcode.interview100;

/** 
* @ClassName   : Leetcode0044 
* @author      : ganwei 
* @date        : 2020年5月25日 
* @Description : TODO 
*/
public class Leetcode0044 {
    /**
     * -解题思路，动态规划
     */
	public boolean isMatch(String s, String p) {
		int sLen = s.length(), pLen = p.length();
		boolean[][] dp = new boolean[sLen+1][pLen+1];
		dp[0][0] = true;
		
		//初始化
		for(int i = 1; i <= pLen; i++){
			dp[0][i] = dp[0][i-1] && p.charAt(i-1) == '*';
		}
		
		for(int i = 1; i <= sLen; i++){
			for(int j = 1; j <= pLen; j++){
				if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?'){
					dp[i][j] = dp[i-1][j-1];
				}else if(p.charAt(j-1) == '*'){
					dp[i][j] = dp[i-1][j] || dp[i][j-1];
				}
			}
		}
		
		return dp[sLen][pLen];
    }
	
	/**
	 * -回溯算法
	 */
	public boolean backtrace(String s, String p) {
		
		
		return false;
	}
	
	
	/**
	 * -主函数
	 */
	public static void main(String[] args) {
		
	}
}
